#include "TestLinkList.h"

TestLinkLIst::TestLinkLIst():head(new Node),size(0)
{
    head->data = 0;
    head->next = nullptr;
}

TestLinkLIst::~TestLinkLIst()
{
    while(head != nullptr)
    {
        Node * nextNode = head->next;
        delete head;
        head = nextNode;
    }
}

inline Node* CreateNode(ElementType element)
{
    Node * newNode = new Node;
    newNode->data = element;
    newNode->next = nullptr; 
    return newNode;
}

void TestLinkLIst::InsertTail(ElementType element)
{
    Node * travelPoint = head;
    while(travelPoint->next != nullptr)
    {
        travelPoint = travelPoint->next;
    }
    travelPoint->next = CreateNode(element);
    size++;
}

void TestLinkLIst::InsertHead(ElementType element)
{
    Node * newNode = CreateNode(element);
    newNode->next = head->next;
    head->next = newNode;
    size++;
}

void TestLinkLIst::InsertByIndex(int index, ElementType element)
{
    Node * travelPoint = head;
    for(int i = 0; i < index; i++)
    {
        travelPoint  = travelPoint->next;
    }
    Node * newNode = CreateNode(element);
    newNode->next = travelPoint->next;
    travelPoint->next = newNode;
    size++;
}

void TestLinkLIst::RemoveByIndex(int index)
{
    Node * travelPoint = head;
    for(int i = 0; i < index; i++)
    {
        travelPoint  = travelPoint->next;
    }
    Node * freeNode = travelPoint->next;
    travelPoint->next = freeNode->next;
    delete freeNode;
    size--;
}

void TestLinkLIst::RemoveByElement(ElementType element)
{
    Node * travelPoint = head;
    while(travelPoint->next != nullptr)
    {
        if(travelPoint->next->data == element)
        {
            Node *freeNode = travelPoint->next;
            travelPoint->next = freeNode->next;
            delete freeNode;
            size--;
        }
        else
            travelPoint = travelPoint->next;
    }
}

void TestLinkLIst::UpdataByIndex(int index, ElementType newValue)
{
    Node * travelPoint = head;
    for(int i = 0; i <= index; i++)
    {
        travelPoint  = travelPoint->next;
    }
    travelPoint->data = newValue;
}

void TestLinkLIst::UpdataByElement(ElementType oldValue, ElementType newValue)
{
    Node * travelPoint = head;
    while(travelPoint->next != nullptr)
    {
        if(travelPoint->next->data == oldValue)
        {
            travelPoint->next->data = newValue;
        }
        travelPoint = travelPoint->next;
    }
}

ElementType &TestLinkLIst::operator[](int index)
{
     Node * travelPoint = head;
    for(int i = 0; i <= index; i++)
    {
        travelPoint  = travelPoint->next;
    }
    return travelPoint->data;
}

void TestLinkLIst::BubbleSort()
{
    for(int i = 0; i < size - 1; i++)
    {
       Node * travelPoint = head;
       for(int j = 0; j < size - i - 1; j++)
       {
            
            if(travelPoint->next->data > travelPoint->next->next->data)
            {
                Node *Prev = travelPoint->next;
                Node *Next = Prev->next;
                Prev->next = Next->next;
                Next->next = Prev;
                travelPoint->next = Next;
            }
            travelPoint = travelPoint->next;
       } 
    }
}

void TestLinkLIst::FastSort()
{
    FastSort(head->next,nullptr);
}

TestLinkLIst TestLinkLIst::Merge(const TestLinkLIst &l)
{
    TestLinkLIst result;
    Node * p1 = this->head->next;
    Node * p2 = l.head->next;
    while(p1 && p2)
    {
        if(p1->data < p2->data)
        {
            result.InsertTail(p1->data);
            p1 = p1->next;
        }
        else
        {
            result.InsertTail(p2->data);
            p2 = p2->next;
        }
    }
    while (p1)
    {
        result.InsertTail(p1->data);
        p1 = p1->next;
    }
    while(p2)
    {
        result.InsertTail(p2->data);
        p2 = p2->next;
    }
    return result;
}

void TestLinkLIst::Reserve()
{
    Node * prev = nullptr;
    Node * cur = head->next;
    Node * Next = cur->next;
    while(Next != nullptr)
    {
        cur->next = prev;
        prev = cur;
        cur = Next;
        Next = cur->next;
    }
    cur->next = prev;
    head->next = cur;
}

void TestLinkLIst::show()
{
    Node * travelPoint = head;
    while(travelPoint->next != nullptr)
    {
        std::cout<<travelPoint->next->data<<" ";
        travelPoint = travelPoint->next;
    }
    std::cout<<std::endl;
}

void TestLinkLIst::FastSort(Node *start, Node *end)
{
    if(start == end)
        return;
        Node * temp = start;
        Node * p1 = start;
        Node * p2 = p1->next;

        while(p2 != end)
        {
            if(p2->data < temp->data)
            {
                p1 = p1->next;
                std::swap(p1->data,p2->data);
            }
            p2 = p2->next;
        }
        std::swap(p1->data,temp->data);
    FastSort(start,p1);
    FastSort(p1->next,end);
}

Node *TestLinkLIst::Reserve2(Node *node)
{
    

    return nullptr;
}
